import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution2183 {
    long count=0;
    Map<List<Integer>,Long> map=new HashMap<>();

    public long countPairs(int[] nums, int k) {
        Map<Integer,Integer> con=new HashMap<>();
        for (int i=2;i<=(int)Math.sqrt(k);i++){
            while (k%i==0){
                con.put(i,con.getOrDefault(i,0)+1);
                k=k/i;
            }
        }
        if (k!=1){
            con.put(k,1);
        }
        List<Integer> list=new ArrayList<>(con.keySet());
        for (int i=0;i<nums.length;i++){
            List<Integer> m=new ArrayList<>();
            for (int j=0;j<list.size();j++){
                int t=0;
                while (nums[i]%list.get(j)==0){
                    t++;
                    nums[i]/=list.get(j);
                }
                m.add(t);
            }
            List<Integer> v=new ArrayList<>();
            for (int j=0;j<list.size();j++){
                v.add(Math.max(0,con.get(list.get(j))-m.get(j)));
            }
            count+=map.getOrDefault(v,0L);
            List<Integer> temp=new ArrayList<>();
            dfs(0,m,temp);
        }

        return count;
    }

    void dfs(int k,List<Integer> m,List<Integer> temp){
        if (k==m.size()){
            map.put(new ArrayList<>(temp),map.getOrDefault(temp,0L)+1);
            return;
        }
        for (int i=0;i<=m.get(k);i++){
            temp.add(i);
            dfs(k+1,m,temp);
            temp.remove(temp.size()-1);
        }
    }


    public static void main(String[] args) {
        System.out.println(new Solution2183().countPairs(new int[]{1,2,3,4,5},2));
    }
}
